package sort;

import java.nio.charset.MalformedInputException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 * 查找算法
 */
public class find {
    public static void main(String[] args) {
        int[] arr = {1, 6, 7, 89, 111, 1000, 1000, 1000, 1234};
//        System.out.println(find(arr, 0, arr.length - 1, 1000));
        System.out.println(finds(arr, 0, arr.length - 1, 1000));

        int[] arr1 = new int[100];
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = i + 1;
        }
        System.out.println(InsertFind(arr1, 0, arr1.length - 1, 100));
        System.out.println(fiboFind(arr1,100));

    }

    /**
     * 斐波那契查找，
     * 先把数组扩容到斐波拉契的长度，在数组最后补最大值，一直补满。
     * f[k]=f[k-1]+f[k-2]
     *
     * f[k]-1 =(f[k-1] - 1)+(f[k-2]-1)+1
     *
     *
     * f[k-1] mid f[k-2]
     *
     * @param arr
     * @param key
     * @return
     */
    private static int fiboFind(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int k = 0, mid = 0;
        int f[] = fib(100000);
        while (high > f[k] - 1) {
            k++;
        }
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }

        while (low<=high){
            mid=low+f[k-1]-1;
            if (key<temp[mid]){
                high=mid-1;
                k--;
            }else if (key >temp[mid]){
                low=mid+1;
                k-=2;
            }else {
                if (mid<=high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }

    /**
     * 斐波那契数列
     *
     * @param maxSize
     * @return
     */
    private static int[] fib(int maxSize) {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * 数据量大，且分布比较均匀的时候用查找查找
     * 查找查找，优化的二分查找
     * 自适应mid，连续的有序数组
     * 优化中间值：
     * mid=l+(l+r)*(v-arr[l)/(arr[r]-arr[l])
     *
     * @param arr
     * @param l
     * @param r
     * @param value
     * @return
     */
    private static int InsertFind(int[] arr, int l, int r, int value) {
        if (l > r || value < arr[0] || value > arr[arr.length - 1]) {
            return -1;
        }
        int mid = l + (r - l) * (value - arr[l]) / (arr[r] - arr[l]);
        if (value > arr[mid]) {
            return InsertFind(arr, mid + 1, r, value);
        } else if (value < arr[mid]) {
            return InsertFind(arr, l, mid - 1, value);
        } else {
            return mid;
        }
    }


    /**
     * 有序数组的二分查找
     * 查找多个相同值得下标
     *
     * @param arr
     * @param value
     * @return
     */
    private static List<Integer> finds(int[] arr, int l, int r, int value) {
        if (l > r) {
            return new ArrayList();
        }
        int mid = (l + r) / 2;
        if (value > arr[mid]) {
            return finds(arr, mid + 1, r, value);
        } else if (value < arr[mid]) {
            return finds(arr, l, mid - 1, value);
        } else {
            List<Integer> res = new ArrayList<>();
            List<Integer> list1 = finds(arr, l, mid - 1, value);
            List<Integer> list2 = finds(arr, mid + 1, r, value);
            res.add(mid);
            res.addAll(list1);
            res.addAll(list2);
            return res;
        }
    }


    /**
     * 有序数组的二分查找
     *
     * @param arr
     * @param value
     * @return
     */
    private static int find(int[] arr, int l, int r, int value) {
        if (l > r) {
            return -1;
        }
        int mid = (l + r) / 2;
        if (value > arr[mid]) {
            return find(arr, mid + 1, r, value);
        } else if (value < arr[mid]) {
            return find(arr, l, mid - 1, value);
        } else {
            return mid;
        }
    }

}
